Mi manual de algoritmos/version_actual/src/geometria/grahamscan.cpp

   1 //Graham scan: Complexity: O(n log n)
   2 struct point{
   3   int x,y;
   4   point() {}
   5   point(int X, int Y) : x(X), y(Y) {}
   6 };
   7
   8 point pivot;
   9
  10 inline int distsqr(const point &a, const point &b){
  11   return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  12 }
  13
  14 inline double dist(const point &a, const point &b){
  15   return sqrt(distsqr(a, b));
  16 }
  17
  18 //retorna > 0 si c esta a la izquierda del segmento AB
  19 //retorna < 0 si c esta a la derecha del segmento AB
  20 //retorna == 0 si c es colineal con el segmento AB
  21 inline
  22 int cross(const point &a, const point &b, const point &c){
  23   return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
  24 }
  25
  26 //Self < that si esta a la derecha del segmento Pivot-That
  27 bool angleCmp(const point &self, const point &that){
  28   int t = cross(pivot, that, self);
  29   if (t < 0) return true;
  30   if (t == 0){
  31     //Self < that si está más cerquita
  32     return (distsqr(pivot, self) < distsqr(pivot, that));
  33   }
  34   return false;
  35 }
  36
  37 vector<point> graham(vector<point> p){
  38   //Metemos el más abajo más a la izquierda en la posición 0
  39   for (int i=1; i<p.size(); ++i){
  40     if (p[i].y < p[0].y ||
  41         (p[i].y == p[0].y && p[i].x < p[0].x))
  42       swap(p[0], p[i]);
  43   }
  44
  45   pivot = p[0];
  46   sort(p.begin(), p.end(), angleCmp);
  47
  48   //Ordenar por ángulo y eliminar repetidos.
  49   //Si varios puntos tienen el mismo angulo el más lejano
  50   //queda después en la lista
  51   vector<point> chull(p.begin(), p.begin()+3);
  52
  53   //Ahora sí!!!
  54   for (int i=3; i<p.size(); ++i){
  55     while (chull.size() >= 2 &&
  56            cross(chull[chull.size()-2],
  57                  chull[chull.size()-1],
  58                  p[i]) <=0){
  59       chull.erase(chull.end() - 1);
  60     }
  61     chull.push_back(p[i]);
  62   }
  63   //chull contiene los puntos del convex hull ordenados
  64   //anti-clockwise.  No contiene ningún punto repetido.  El
  65   //primer punto no es el mismo que el último, i.e, la última
  66   //arista va de chull[chull.size()-1] a chull[0]
  67   return chull;
  68 }